PittsburghV1, Main, Exploration, bibRecord, 000031

Complexity of Manipulating Sequential Allocation

Identifieur interne : 000031 ( Main/Exploration ); précédent : 000030; suivant : 000032

Complexity of Manipulating Sequential Allocation

Auteurs : Haris Aziz [Australie] ; Sylvain Bouveret [France] ; Jérôme Lang [France] ; Simon Mackenzie [États-Unis]

Source :

RBID : Hal:hal-01501842

Descripteurs français

mix :
- game theory, manipulation, resource allocation, sequential allocation, social choice.

Abstract

Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several non-manipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.

Url:

https://hal.archives-ouvertes.fr/hal-01501842

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000719
to stream Hal, to step Curation: 000719
to stream Hal, to step Checkpoint: 000031
to stream Main, to step Merge: 000031
to stream Main, to step Curation: 000031

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr">Complexity of Manipulating Sequential Allocation</title>
<author><name sortKey="Aziz, Haris" sort="Aziz, Haris" uniqKey="Aziz H" first="Haris" last="Aziz">Haris Aziz</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-134757" status="INCOMING">          <orgName>University of South Wales</orgName>
          <desc>            <address>              <country key="AU"></country>
            </address>
          </desc>
          <listRelation>            <relation active="#struct-332681" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-332681" type="direct"><org type="institution" xml:id="struct-332681" status="INCOMING">          <orgName>University of South Wales</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Australie</country>
</affiliation>
</author>
<author><name sortKey="Bouveret, Sylvain" sort="Bouveret, Sylvain" uniqKey="Bouveret S" first="Sylvain" last="Bouveret">Sylvain Bouveret</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-5032" status="INCOMING">          <orgName>Institut national Polytechnique de Grenoble</orgName>
          <orgName type="acronym">INP GRENOBLE</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inpg.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-300275" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-300275" type="direct"><org type="institution" xml:id="struct-300275" status="OLD">          <idno type="IdRef">026388804</idno>
          <orgName>Institut National Polytechnique de Grenoble </orgName>
          <orgName type="acronym">INPG</orgName>
          <date type="end">2006-12-31</date>
          <desc>            <address>              <addrLine>46 avenue Félix Viallet 38031 Grenoble Cedex 1</addrLine>
              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Lang, Jerome" sort="Lang, Jerome" uniqKey="Lang J" first="Jérôme" last="Lang">Jérôme Lang</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-989" status="VALID"><orgName>Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision</orgName>
<orgName type="acronym">LAMSADE</orgName>
<desc><address><addrLine>Place de Lattre de Tassigny 75775 PARIS CEDEX 16</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lamsade.dauphine.fr/</ref>
</desc>
<listRelation><relation active="#struct-300302" type="direct"></relation>
<relation name="UMR7024" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300302" type="direct"><org type="institution" xml:id="struct-300302" status="VALID"><orgName>Université Paris-Dauphine</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR7024" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Mackenzie, Simon" sort="Mackenzie, Simon" uniqKey="Mackenzie S" first="Simon" last="Mackenzie">Simon Mackenzie</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87723" status="VALID">          <orgName>Computer Science Department - Carnegie Mellon University</orgName>
          <desc>            <address>              <addrLine>Computer Science Department Carnegie Mellon University Pittsburgh, PA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cs.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-378064" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING">          <orgName>University of Pittsburgh</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01501842</idno>
<idno type="halId">hal-01501842</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-01501842</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-01501842</idno>
<date when="2017-02">2017-02</date>
<idno type="wicri:Area/Hal/Corpus">000719</idno>
<idno type="wicri:Area/Hal/Curation">000719</idno>
<idno type="wicri:Area/Hal/Checkpoint">000031</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000031</idno>
<idno type="wicri:Area/Main/Merge">000031</idno>
<idno type="wicri:Area/Main/Curation">000031</idno>
<idno type="wicri:Area/Main/Exploration">000031</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="fr">Complexity of Manipulating Sequential Allocation</title>
<author><name sortKey="Aziz, Haris" sort="Aziz, Haris" uniqKey="Aziz H" first="Haris" last="Aziz">Haris Aziz</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-134757" status="INCOMING">          <orgName>University of South Wales</orgName>
          <desc>            <address>              <country key="AU"></country>
            </address>
          </desc>
          <listRelation>            <relation active="#struct-332681" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-332681" type="direct"><org type="institution" xml:id="struct-332681" status="INCOMING">          <orgName>University of South Wales</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Australie</country>
</affiliation>
</author>
<author><name sortKey="Bouveret, Sylvain" sort="Bouveret, Sylvain" uniqKey="Bouveret S" first="Sylvain" last="Bouveret">Sylvain Bouveret</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-5032" status="INCOMING">          <orgName>Institut national Polytechnique de Grenoble</orgName>
          <orgName type="acronym">INP GRENOBLE</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.inpg.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-300275" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-300275" type="direct"><org type="institution" xml:id="struct-300275" status="OLD">          <idno type="IdRef">026388804</idno>
          <orgName>Institut National Polytechnique de Grenoble </orgName>
          <orgName type="acronym">INPG</orgName>
          <date type="end">2006-12-31</date>
          <desc>            <address>              <addrLine>46 avenue Félix Viallet 38031 Grenoble Cedex 1</addrLine>
              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Lang, Jerome" sort="Lang, Jerome" uniqKey="Lang J" first="Jérôme" last="Lang">Jérôme Lang</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-989" status="VALID"><orgName>Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision</orgName>
<orgName type="acronym">LAMSADE</orgName>
<desc><address><addrLine>Place de Lattre de Tassigny 75775 PARIS CEDEX 16</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lamsade.dauphine.fr/</ref>
</desc>
<listRelation><relation active="#struct-300302" type="direct"></relation>
<relation name="UMR7024" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300302" type="direct"><org type="institution" xml:id="struct-300302" status="VALID"><orgName>Université Paris-Dauphine</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR7024" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Mackenzie, Simon" sort="Mackenzie, Simon" uniqKey="Mackenzie S" first="Simon" last="Mackenzie">Simon Mackenzie</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87723" status="VALID">          <orgName>Computer Science Department - Carnegie Mellon University</orgName>
          <desc>            <address>              <addrLine>Computer Science Department Carnegie Mellon University Pittsburgh, PA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cs.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-378064" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING">          <orgName>University of Pittsburgh</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>game theory</term>
<term>manipulation</term>
<term>resource allocation</term>
<term>sequential allocation</term>
<term>social choice</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several non-manipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.</div>
</front>
</TEI>
<affiliations><list><country><li>Australie</li>
<li>France</li>
<li>États-Unis</li>
</country>
<region><li>Pennsylvanie</li>
</region>
<settlement><li>Pittsburgh</li>
</settlement>
<orgName><li>Université de Pittsburgh</li>
</orgName>
</list>
<tree><country name="Australie"><noRegion><name sortKey="Aziz, Haris" sort="Aziz, Haris" uniqKey="Aziz H" first="Haris" last="Aziz">Haris Aziz</name>
</noRegion>
</country>
<country name="France"><noRegion><name sortKey="Bouveret, Sylvain" sort="Bouveret, Sylvain" uniqKey="Bouveret S" first="Sylvain" last="Bouveret">Sylvain Bouveret</name>
</noRegion>
<name sortKey="Lang, Jerome" sort="Lang, Jerome" uniqKey="Lang J" first="Jérôme" last="Lang">Jérôme Lang</name>
</country>
<country name="États-Unis"><region name="Pennsylvanie"><name sortKey="Mackenzie, Simon" sort="Mackenzie, Simon" uniqKey="Mackenzie S" first="Simon" last="Mackenzie">Simon Mackenzie</name>
</region>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000031 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000031 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Hal:hal-01501842
   |texte=   Complexity of Manipulating Sequential Allocation
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

Complexity of Manipulating Sequential Allocation

Complexity of Manipulating Sequential Allocation

Source :

Descripteurs français

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri